1. Field of the Invention
This invention relates to computer memory arrangements and, more particularly, to methods for equalizing the amount of switching accomplished in different parts of a flash electrically erasable programmable read only memory (flash EEPROM) array.
2. History of the Prior Art
Modern computer systems make extensive use of long term memory. Typically this memory is provided by one or more hard (fixed) disks. A hard disk is an electro-mechanical device which includes one or more flat circular disks fixed to rotate rapidly about a central axis. Each flat disk has opposite surfaces which are coated with some form of magnetic material. A mechanical arm driven by electrical signals places a magnetic head over each side of each disk to write to positions on the disk or to read from those positions. These positions lie in sectors, a number of which (e.g., seventeen) form one complete track on one side of a disk. Each sector is capable of storing a fixed number of bytes of data (typically 512 bytes). Depending on formatting, a single side of a disk may have over six hundred tracks. A typical disk drive used in personal computers today is capable of storing forty megabytes of data.
Such hard disk drives are very useful and have become almost a necessity to the operation of personal computers. However, such electro-mechanical drives do have their drawbacks. They are relatively heavy and increase the weight of a computer, especially a portable computer, significantly. They also are relatively bulky and require a significant amount of space within a computer. Their use requires a significant amount of the power and in a portable computer leads to significant battery power consumption. More importantly, electro-mechanical hard disk drives are very susceptible to shock. A hard drive within a portable computer which is dropped is quite likely to cease functioning. This can cause a catastrophic loss of data.
Recently, forms of long term storage other than electromechanical hard disks have become feasible for use in computers. One of these is flash EEPROM. Flash EEPROM memory is comprised of a large plurality of floating-gate field effect transistors arranged as memory cells in typical row and column fashion with circuitry for accessing individual cells and placing the memory transistors of those cells in one of two memory conditions. A flash memory cell, like a typical EPROM cell but in contrast to DRAM memory, retains information when power is removed. Flash EEPROM memory has a number of characteristics which adapt it to use as long term memory. It is light in weight, occupies very little space, and consumes less power than electromechanical disk drives. More importantly, it is especially rugged. It will withstand without adverse effects repeated drops each of which would destroy a typical electromechanical hard disk drive.
A difficulty with flash EEPROM, however, is that it is not reprogrammable until it has been erased. Flash EEPROM is erased by applying a high voltage simultaneously to the source terminals of all of the transistors (cells) used in the memory. Because these source terminals are all connected to one another by metallic busing in the array, the entire array must be erased at once. While an electromechanical hard disk will typically store information in a first area of the disk and then rewrite that same area of the disk when the information changes, this is not possible with a flash memory array without erasing all of the valid information that remains in the array along with the invalid (dirty) information. If all of the information is erased each time a single entry has to be rewritten, then all of the valid information which was erased must also be rewritten with each update. As may be appreciated, such a process used to update entries as the data changes would significantly slow the operation of any computer system using flash memory in place of an electro-mechanical hard disk. Moreover, partly because of the need to rewrite valid information, the erase process for flash EEPROM is quite slow; it typically requires between one and two seconds. Such an erase time would seem to preclude the use of flash EEPROM for rapidly changing data.
Thus, when a flash EEPROM array is to be used for long term storage where data is rapidly changing as is the case with the information typically stored by an electro-mechanical hard disk, some method of erasing and rewriting the flash array must be devised which is different than that typically used for electro-mechanical hard disks and does not slow the operation of the system.
It has been found possible to reduce the amount of flash memory which must be erased at once by physically separating the flash array during chip layout into groups (blocks) of cells which may be erased together. This type of arrangement reduces the reprogramming effort to some extent but it may be used only in a limited manner because the individual blocks of cells must be physically isolated on the silicon in order to allow the blocks to be flash erased separately. The physical isolation required increases the necessary area to hold such blocks of flash memory.
For example, a new arrangement using such a division of flash memory into isolated blocks is disclosed is U.S. patent application Ser. No 969,131, entitled Method and Circuitry for a Solid State Memory Disk, S. Wells, filed on even date herewith, and assigned to the assignee of the present invention. In that arrangement, a typical long term storage array is comprised of flash memory arranged in a series of blocks. In one embodiment, the array is divided into a number of silicon chips each of which is subdivided into sixteen subblocks. Each subblock is, in fact, physically paired with a subblock on another of the silicon chips to create a logical block of the array in which odd bytes of data are stored on the subblock of one chip and even bytes of data are stored on the subblock of the other chip. Each of the logical blocks of flash memory is separately erasable from all other such blocks. However, each of the logical blocks of the array typically holds 128 kilobytes of data, sufficient to hold 256 sectors of information normally stored on the tracks of an electromechanical hard disk drive. Thus, a thirty chip flash array with sixteen individually-erasable subblocks per chip holds about the same amount of data as does a thirty megabyte electro-mechanical hard disk. Even with this division of data into 240 individually-erasable parts (logical blocks), erasure of a block effects erasure of such a very large amount of information that to attempt to erase all of the data and then replace the valid data with each rewrite of a sector would not be feasible.
In order to overcome this problem, data is written to any block of the flash memory array which has space available. Thus, data is written to an empty position in the array no matter what the sector address of the data or the physical address on the block. A piece of data to be written to a sector five, for example, is written to the next available space on a block being written no matter where that may be; and a lookup table is kept which records the physical position on the block of the logical address (sector five). This arrangement of the array allows a first block to be written sector by sector, a second block to be written in the same sequential manner, and so on. When the data in a sector changes so that the sector needs to be rewritten, the data is written to a new physical position, the data in the lookup table is changed to record the new physical position against the logical sector number, and the first position at which the data was written is marked as dirty so that an attempt to read that physical position produces an error signal. After some period of time, a sufficient number of blocks will be filled that it will be desirable to release space by moving the valid information from some especially dirty block to some other block and erasing the entire block from which the valid information has been read. This is referred to as "cleaning up a block" and has the effect of freeing up an additional number of sectors equal to all of the sectors on the erased block which have previously been marked as dirty.
An especial advantage of the arrangement is that it allows the erasure of blocks to occur in the background. That is, since invalid individual entries are not erased as they are rewritten, erasure may be arranged to occur when the facilities of the array are not otherwise occupied with reading and writing. In this manner, the external host which is writing to and receiving information from the flash array is typically not aware that an erasure is taking place even though the erasure requires one or two seconds.
Another advantage of the arrangement is that the individual blocks of flash memory store sectors of data in physical areas which may be of any size rather than the fixed size sectors stored by electro-mechanical hard disks. This essentially eliminates the lost space typical of hard and floppy disks with their fixed size sectors because each individual sector of data placed on a block of flash memory need only be as long as the space required to store the data. Thus, sectors may be placed on a block of flash memory essentially abutted against a last valid byte of data from the last sector stored with a space left blank between sectors which averages only one byte of data. When data is compressed, it may take substantially less space than that required for storing the uncompressed data of a 512 byte sector. The space normally left at the end of a sector of fixed physical size may be eliminated when data is compressed. This elimination of waste storage space along with other attributes of the arrangement allows flash memory storing data at a compression rate of 1.5 to store the same amount of data in approximately three quarters as much physical storage space as is stored by a typical electromechanical hard disk of a given size.
A problem exhibited by flash memory is that it tends to have a limited life in use. This would seem to be due to the floating-gate transistors of the array requiring longer to switch after undergoing some number of switching operations. This number is quite large; it has been estimated that although switching begins to take longer after approximately ten thousand switching operation, approximately one hundred thousand switching operations are required before the extended switching time has any affect on system operation. Even so, the typical processes used to select the cells in which data is to be stored tend to cause certain transistors on a block and certain blocks of transistors to switch more often than do other transistors. Studies indicate that certain areas of a flash memory array such as those blocks in which application programs are stored are subject to very infrequent rewriting. On the other hand, blocks where data is accumulated for a particular operation by an application program change and must be rewritten very frequently. Moreover, since the blocks which store rapidly changing data have more dirty sectors than do other blocks, those blocks will be cleaned up more often. Once a block has been cleaned up during operation, it is much more likely to receive rapidly changing data than it is to receive data which does not change. Consequently, a block containing data initially subject to rapid change will automatically be subject to additional rapid change due to the nature of the data architecture. Changing data necessitates the cleanup of such blocks. Consequently, a particular block may be subject to much more rapid failure than other blocks if something is not done to equalize the amount of switching over the entire array.
An arrangement for controlling the number of switching cycles to which each block of a flash memory is subject is very desirable. Such an arrangement would go far toward correcting the statistical vagaries which might otherwise induce certain portions of a flash memory array to experience early failure.